package com.origin.niuke.linkedlist;

import general_class.ListNode;

/**
 * @author yzh
 * @version 1.0
 * @date 2022/5/17 19:58
 * 判断一个链表是否为回文结构
 * 算法：链表 + 快慢指针
 */
public class NC96 {

    public boolean isPail (ListNode head) {
        // write code here
        ListNode s = head, f = head;
        while (f != null && f.next != null) {
            s = s.next;
            f = f.next.next;
        }
        f = reverse(s);
        while (head != null && f != null) {
            if (head.val != f.val) return false;
            head = head.next;
            f = f.next;
        }
        return true;
    }
    ListNode reverse(ListNode node) {
        ListNode pre = null;
        while (node != null) {
            ListNode next = node.next;
            node.next = pre;
            pre = node;
            node = next;
        }
        return pre;
    }

}
